import java.util.Stack;

/**
 * Created with IntelliJ IDEA
 * Description:
 * User: Administrator
 * Data: 2023 - 08 - 30
 * Time: 11:09
 */
//牛客 序列化二叉树
public class Solution4 {
    //官方推荐方法
    int index = 0;
    String Serialize(TreeNode root) {
        if(root == null) return "#";
        return SerializeF(root).toString();
    }
    public StringBuilder SerializeF(TreeNode root) {
        StringBuilder s = new StringBuilder();//递归有返回值时，stringBuilder要设置成递归函数里的局部变量；没有返回值时则设置在递归函数外（如全局变量和非全局变量）
        if(root == null) return s.append("#");
        s.append(root.val).append("!");
        StringBuilder s1 = SerializeF(root.left);
        StringBuilder s2 = SerializeF(root.right);
        return s.append(s1).append(s2);
    }
    TreeNode Deserialize(String str) {
        if(str.equals("#")) {
            return null;
        }
        return DeserializeF(str);
    }
    TreeNode DeserializeF(String str) {
        if(str.charAt(index) == '#') {
            index++;
            return null;
        }
        int val = 0;
        while (str.charAt(index) != '!') {
            val = val * 10 + (str.charAt(index) - '0');
            index++;
        }
        TreeNode root = new TreeNode(val);
        index++;//跳过！
        root.left = DeserializeF(str);
        root.right = DeserializeF(str);
        return root;
    }
}
